#include <iostream>
#include <string>
using namespace std;

bool matchCore(const string &str, int str_idx,
    const string &pattern, int pattern_idx) {
  if (str_idx == str.size() && pattern_idx == pattern.size()) {
    return true;
  }
  if (str_idx == str.size() || pattern_idx == pattern.size()) {
    return false;
  }
  bool ret = 0;
  if (pattern_idx + 1 < pattern.size() && pattern[pattern_idx + 1] == '*') {
    if (str[str_idx] == pattern[pattern_idx] || pattern[pattern_idx] == '.') {
      ret = matchCore(str, str_idx + 1, pattern, pattern_idx + 2) ||  // 匹配一个
            matchCore(str, str_idx, pattern, pattern_idx + 2) ||  // 匹配零个
            matchCore(str, str_idx + 1, pattern, pattern_idx);  // 匹配多个
    } else {
      ret = matchCore(str, str_idx, pattern, pattern_idx + 2);
    }
  } else if (str[str_idx] == pattern[pattern_idx] || pattern[pattern_idx] == '.') {
    ret = matchCore(str, str_idx + 1, pattern, pattern_idx + 1);
  } else {
    ret = false;
  }
  return ret;
}

bool match(const string &str, const string &pattern) {
  return matchCore(str, 0, pattern, 0);
}

int main() {
  cout << "match aaa and a.a: " << match("aaa", "a.a") << endl;
  cout << "match aaa and ab*ac*a: " << match("aaa", "ab*ac*a") << endl;
  cout << "match aa.a and ab*a: " << match("aa.a", "ab*a") << endl;
  return 0;
}
